LeetCode 77、组合

一、题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        List<Integer> path = new ArrayList<>();

        backtrack( n , k , path , 1 );

        return res;
    }

    // 1、画出递归树，找到状态变量(回溯函数的参数)
    private void backtrack(int n,int k,List<Integer> path,int start) {
        
        // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if(k == 0 ){
            
            // 找到一个组合了
            res.add(new ArrayList(path));

            return;
        }
            
        // 3、确定选择列表，即需要把什么数据存储到结果里面
        // for 循环就是一个选择的过程
 
        for (int i = start ; i <= n - k + 1 ; i++ ) {
            
            // 当前路径上可以把 nums[i] 加上
            path.add(i);
        
            // 一些逻辑操作（可有可无，视情况而定）
            // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            // 需要剪枝
            // 此时，目标值 target，已经从 target 变成了 target - nums[i]
            // 接下来需要去【某个区间中】拼凑 target - nums[i]
            // 由于 同一个 数字可以 无限制重复被选取
            // 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，依旧可以继续从使用 nums[i] 开始
            // 而 i 前面的元素，比如 num[i-1]、 num[i-2]无法继续使用，实现了剪枝操作
            int nowposition = i + 1 ; 

            // 5、做出选择，递归调用该函数，进入下一层继续搜索
            // 递归
            backtrack(n, k - 1 , path , nowposition );
        
            // 一些逻辑操作（可有可无，视情况而定）

            // 6、撤销选择，回到上一层的状态
            path.remove(path.size()-1);
        }
    }
}

Python代码

class Solution:

    def __init__(self):
        self.res = []

    def combine(self, n: int, k: int) -> List[List[int]]:
        """
        :param n: int
        :param k: int
        :return: List[List[int]]
        """
        path = []

        self.backtrack(n, k, path, 1)

        return self.res

    # 1、画出递归树，找到状态变量(回溯函数的参数)
    def backtrack(self, n: int, k: int, path: List[int], start: int) -> None:
        # 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        if k == 0:
            # 找到一个组合了
            self.res.append(list(path))
            return
        
        # 3、确定选择列表，即需要把什么数据存储到结果里面
        # for 循环就是一个选择的过程
        for i in range(start, n - k + 1 + 1):
            # 当前路径上可以把 nums[i] 加上
            path.append(i)
            # 一些逻辑操作（可有可无，视情况而定）
            # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            # 需要剪枝
            # 此时，目标值 target，已经从 target 变成了 target - nums[i]
            # 接下来需要去【某个区间中】拼凑 target - nums[i]
            # 由于 同一个 数字可以 无限制重复被选取
            # 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，依旧可以继续从使用 nums[i] 开始
            # 而 i 前面的元素，比如 num[i-1]、 num[i-2]无法继续使用，实现了剪枝操作
            now_position = i + 1
            # 5、做出选择，递归调用该函数，进入下一层继续搜索
            # 递归
            self.backtrack(n, k - 1, path, now_position)
            # 一些逻辑操作（可有可无，视情况而定）
            # 6、撤销选择，回到上一层的状态
            path.pop()